package leetcode.tencent;

/**
 * @author Cheng Jun
 * Description: 找到一个 String 数组的 最长公共前缀。
 * https://leetcode-cn.com/problems/longest-common-prefix/
 * 贪心算法 入门案例 经典例题
 * @version 1.0
 * @date 2021/11/8 21:03
 */
public class longestCommonPrefix {

    // 贪心算法，先将第一个元素作为 最优解，然后求 最优解和第二个元素的 最优解（最长公共前缀）
    static String longestCommonPrefix(String[] strs) {
        // 特殊情况，只有一个元素就直接返回
        if (strs.length == 1) {
            return strs[0];
        }
        String commonPrefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            // 找到第一个元素和第二个元素的公共前缀，然后将这个公共前缀和第三个数组比较找新的公共前缀，以此类推
            while (!strs[i].startsWith(commonPrefix)) {
                commonPrefix = commonPrefix.substring(0, commonPrefix.length() - 1);
            }
        }
        return commonPrefix;
    }
}
